#include <stdio.h>
#include <stdlib.h>
#define m 3
typedef struct b_tree
{
    int tag;               //标记节点中关键字个数
    int key[m + 1];        //0号地址未用 或者标记节点中关键字个数
    struct b_tree *parent; //指向双亲节点
    struct b_tree *ptr[m + 1];
};

typedef struct result
{
    b_tree *p;
    int i;
    int tag; //0 not found
};

result sreach(b_tree *root, int k)
{
    /*
        查找关键字，若找到，返回(p,i,1) 表示节点p的第i个关键字
        否则返回(p,i,0),表示节点插入位置在第i个节点和第i+1个节点之间
    */
    result r;
    r.p = root;
    r.i = 0;
    r.tag = 0;
    b_tree *q = NULL;
    while (r.p && r.tag)
    {
        //在p中查找
        while (r.i <= m && r.p->key[r.i] < k)
        {
            r.i++;
        }
        if (r.i > 0 && r.p->key[r.i] == k)
        {
            r.tag = 1;
            return r;
        }
        else
        {
            q = r.p;
            r.p = r.p->ptr[r.i];
        }
    }
    r.p = q; //指向空节点的父节点
    return r;
}
int insert(b_tree *&root, int k)
{
    //1.找到合适点 进行插入
    result r = sreach(root, k);
    if (r.tag)
        return 0; //树中有这个节点 无需再次插入
    else
    {
        }
    //2.若不符合m阶B树 进行分裂
}
int main()
{
    /*******************code*******************/

    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
